发布于 

[学习笔记]后缀数组

[学习笔记]后缀数组

时隔数月，终于又来学些新东西了。这次Camp知识点学到的不多，不过倒是知道了许多需要学的知识点。最近可能此主题的Blog比较多。

算法介绍

基础知识

在许多题目中，我们经常需要对一个字符串的子串作许多查询操作，而此时后缀树，后缀自动机和后缀数组之类的数据结构就可以大幅度的帮我们节省时间。其中，后缀数组因其实现简单，作用较为丰富且空间占用少广为使用。

后缀数组(Suffix Array)实现的功能是对一个字符串的不同后缀子串进行排序。对于长度为\(len\)的字符串\(s\)，它的后缀\(suffix(i)\)为\(s[i..len]\)。然后，我们通过对这\(len\)个子串进行排序，得到以下的几个数组：

  • sa[]：保存了对字符串\(s\)的所有后缀排序后的结果。sa[i]存储了第\(i\)小的后缀在原串中的起始位置。
  • rank[]：名次数组。rank[i]存储了以\(i\)为起始位置的后缀子串在sa[]中的排名，即sa[rank[i]] = i。

此外，我们假设比较的串为a,b,那么比较操作的定义如下： 1. \(a[i]<b[i]\): \(a<b\); 2. \(a[i]>b[i]\): \(a>b\); 3. \(a[i]=b[i]\): 比较第\(i+1\)位。 4. \(i > len(b)\): \(a>b\); 5. \(i > len(a)\): \(a<b\)。

由此判定条件，我们可以发现由于我们要比较的\(len\)个串由于长度各不相同，所以不可能相等。

此时，我们便可以想出最简单的后缀数组构造方法：写出所有的后缀字串然后进行一遍排序即可。由于排序操作是\(O(n\log n)\)的，并且字串的长度最大为\(n\)，所以时间复杂度为\(O(n^2 \log n)\)。这个时间明显有些大了，这时我们便需要使用倍增的方法进行构造了。

倍增法

当我们对\(n\)个互不关联的长度为\(n\)的字符串进行排序时，我们固然需要\(O(n^2 \log n)\)的时间进行排序。但是，我们这里比较的是后缀子串，所以我们其实可以利用其中的性质。

我们现在假设有一个二维数组rk[i][j]，它代表的是以\(i\)开始的长度为\(2^j\)的子串在长度为\(2^j\)的子串中的排名。当\(2^j \geq len\)时，其实该数组就等于了后缀数组中的rank[]。

那么，我们便只需要迭代地更新rk[][]数组即可。对于rk[i][j]，其代表的是从\(i\)开始的长度为\(2^j\)的子串，那么，\(rk[i][j-1]\)其实就可以作为它的第一关键字，而\(rk[i+2^{j-1}][j-1]\)则是第二关键字。我们按照这些关键字机型排序即可。

倘若我们排序时使用快速排序，那么该算法的时间复杂度便为\(O(n \log ^ 2 n)\)。不过倘如该串是一个字符串或者其它取值范围较小的串，那么我们便可以用奇数排序，这样时间复杂度便变为了\(O(n \log n)\)。

PS: 除了倍增法，还有速度更快的时间复杂度为\(O(n)\)的DC3算法，不过编程难度很高，所以一般不使用。此外，还可以使用hash，对所有的后缀子串进行hash然后排序，其也可以实现\(O(n \log ^2 n)\)的时间复杂度，但是不稳定。

实现细节

我们假设是对一个字符串s[]进行处理，那么我们在这里便使用基数排序。使用buc[]来作基数排序的桶，a-z分别映射1-26。因为我们是迭代更新，所以rk[][]完全可以使用一位数组rank[]代替。不过由于rank[]是保留字，所以我们使用rk[]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

//先做一边基数排序，算出各自的排名
for (int i = 1; i<=n; i++)
    buc[ s[i] - 'a' + 1 ] ++;
for (int i  = 1; i<MAXNCHAR; i++)
    buc[i] += buc[i-1];

//利用基数排序的答案来更新rank[]数组
for (int i = 1; i<=n; i++)
    rk[i] = buc[ a[i] - 'a' ] + 1;

//枚举不同的长度，需要log(n)次运算
for (int t = 1; t <= n; t *= 2)
{
    //更新第一和第二关键字
    for (int i = 1; i<=n; i++)
    {
        first[i] = rk[i];
        second[i] = i+t>n? 0 : rk[i+t];
    }

    //将buc[]数组清0
    fill(buc, buc+n+1, 0);

    //按照第二关键字进行一次基数排序
    for (int i = 1; i<=n; i++)
        buc[ second[i]] ++;
    for (int i = 1; i<=n; i++)
        buc[i] += buc[i-1];

    //用tmp[]来存储按照第二关键字排序的名次，这里我们得到的结果为从大到小排序
    for (int i = 1; i<=n; i++)
        tmp[ n - --buc[ second[i] ] ] = i;

    //将buc[]清0
    fill(buc, buc+n+1, 0);

    //按照第一关键字进行基数排序
    for (int i = 1; i<=n; i++)
        buc[ first[i] ] ++;
    for (int i = 1; i<=n; i++)
        buc[i] += buc[i-1];

    //按照第二关键字排好序的顺序来用buc[]更新sa[]数组，这样可以确保在first[]相同时，second[]最小的子串能够排在后面
    for (int i = 1,j; i<=n; i++)
    {
        j = tmp[i];
        sa[ buc[first[j]]-- ] = j;
    }

    //一个优化：当前如果没有first[]和second[]相同的子串直接退出，因为此时已经等价于最终答案
    bool flag = true;
    //使用sa[]来更新rk[]数组
    int k = 0;
    for (int i = 1; i<=n; i++)
    {
        int j = sa[i];

        if (!k)
            rk[j] = 1;
        else if (first[j]==first[k] && second[j]==second[k])
        {
            rk[j] = rk[k];
            flag = false;
        }else
            rk[j] = rk[k] + 1;

        k = j;
    }

    if (flag)
        break;
}

性质

height[]数组

我们定义height[i]为\(suffix(sa[i])\)和\(suffix(sa[i-1])\)的最长公共前缀长度。很明显，对于一个后缀子串，在sa[]数组中离他越近的最长公共前缀越长。

我们可以利用这个性质。我们假设h[i] = height[ rank[i] ]。那么此时便会存在一个性质\(h[i] \geq h[i-1] - 1\)。所以我们便可以利用此性质\(O(n)\)地计算出height[]数组。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1, k = 0; i <= n; i++)
{
    if (rk[i] == 1) k = 0;
    else
    {
        if (k > 0) k--;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i - 1 + k] == s[j - 1 + k]) 
            k++;
    }
    height[rk[i]] = k;
}

LCP问题

height[]数组只是计算出了相邻两个后缀子串地公共前缀。而当我们想要计算任意两个后缀字串的LCP(Longest Common Prefix)时该怎么办呢？这时候其实也需要利用height[]数组。

对于\(LCP(suffix(i), suffix(j))\)，其值其实就等于\(min( height[i+1], ..., height[j])\)，这样，我们只需要维护一个RMQ即可。

例题

Luogu 3809

题目来源：luogu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <algorithm>
#include <string>

#define MAXN 1000100
#define MAXM 62

using namespace std;

int buc[MAXN];
int sa[MAXN];
int rk[MAXN], tmp[MAXN];
int first[MAXN], second[MAXN];
string s;

int trans(char c)
{
    if (c>='0' && c<='9')
        return c - '0' + 1;
    if (c>='A' && c<='Z')
        return c - 'A' + 11;
    if (c>='a' && c<='z')
        return c - 'a' + 37;
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    int n = s.length();

    for (int i = 1; i<=n; i++)
        buc[ trans(s[i-1]) ] ++;
    for (int i = 1; i<=MAXM; i++)
        buc[i] += buc[i-1];

    for (int i = 1; i<=n; i++)
        rk[i] = buc[ trans(s[i-1]) - 1 ] + 1;

    for (int t = 1; t<n; t *= 2)
    {
        for (int i = 1; i<=n; i++)
        {
            first[i] = rk[i];
            second[i] = i+t>n? 0: rk[i+t];
        }

        fill(buc, buc+n+1, 0);
        for (int i = 1; i<=n; i++)
            buc[ second[i] ] ++;
        for (int i = 1; i<=n; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i<=n; i++)
            tmp[ n - --buc[ second[i] ] ] = i;

        fill(buc, buc+n+1, 0);
        for (int i = 1; i<=n; i++)
            buc[ first[i] ] ++;
        for (int i = 1; i<=n; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i<=n; i++)
        {
            int j = tmp[i];
            sa[ buc[first[j]]-- ] = j;
        }

        //不加这个优化就会TLE
        bool flag = true;
        int k = 0;
        for (int i = 1; i<=n; i++)
        {
            int j = sa[i];

            if (!k)
                rk[j] = 1;
            else if (first[j]==first[k] && second[j]==second[k])
            {
                rk[j] = rk[k];
                flag = false;
            }else
                rk[j] = rk[k] + 1;
                // rk[j] = (first[j]==first[k] && second[j]==second[k])?
                    // rk[k] : rk[k] + 1;

            k = j;
        }
        if (flag)
            break;
    }

    for (int i = 1; i<=n; i++)
        cout << sa[i] << (i==n? "\n": " ");

}

POJ 2774

题目来源：POJ

这题就算是一个LCP问题了，我们只需要将两个字符串合为一个，然后利用height[]数组求即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

#define MAXN 200100
#define MAXM 62
#define INF 0x3f3f3f3f

using namespace std;

int buc[MAXN];
int sa[MAXN];
int rk[MAXN], tmp[MAXN];
int first[MAXN], second[MAXN];
int height[MAXN];
string s;

int trans(char c)
{
    if (c>='a' && c<='z')
        return c - 'a' + 1;
    return 28;
}

int main()
{
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int slen = s.length();
    s += "$";

    string ss;
    cin >> ss;
    s += ss;

    int n = s.length();

    for (int i = 1; i<=n; i++)
        buc[ trans(s[i-1]) ] ++;
    for (int i = 1; i<=MAXM; i++)
        buc[i] += buc[i-1];

    for (int i = 1; i<=n; i++)
        rk[i] = buc[ trans(s[i-1]) - 1 ] + 1;

    for (int t = 1; t<n; t *= 2)
    {
        for (int i = 1; i<=n; i++)
        {
            first[i] = rk[i];
            second[i] = i+t>n? 0: rk[i+t];
        }

        fill(buc, buc+n+1, 0);
        for (int i = 1; i<=n; i++)
            buc[ second[i] ] ++;
        for (int i = 1; i<=n; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i<=n; i++)
            tmp[ n - --buc[ second[i] ] ] = i;

        fill(buc, buc+n+1, 0);
        for (int i = 1; i<=n; i++)
            buc[ first[i] ] ++;
        for (int i = 1; i<=n; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i<=n; i++)
        {
            int j = tmp[i];
            sa[ buc[first[j]]-- ] = j;
        }

        //不加这个优化就会TLE
        bool flag = true;
        int k = 0;
        for (int i = 1; i<=n; i++)
        {
            int j = sa[i];

            if (!k)
                rk[j] = 1;
            else if (first[j]==first[k] && second[j]==second[k])
            {
                rk[j] = rk[k];
                flag = false;
            }else
                rk[j] = rk[k] + 1;
                // rk[j] = (first[j]==first[k] && second[j]==second[k])?
                    // rk[k] : rk[k] + 1;

            k = j;
        }
        if (flag)
            break;
    }

    memset(height, 0, sizeof(0));

    for (int i = 1, k = 0; i <= n; i++)
    {
        if (rk[i] == 1) k = 0;
        else
        {
            if (k > 0) k--;
            int j = sa[rk[i] - 1];
            while (i + k <= n && j + k <= n && s[i - 1 + k] == s[j - 1 + k]) 
                k++;
        }
        height[rk[i]] = k;
    }

    int ans = 0;
    for (int i = 1; i<=n; i++)
        if((sa[rk[i]]>slen&&sa[rk[i]-1]<slen)||(sa[rk[i]]<slen&&sa[rk[i]-1]>slen))
            ans=max(ans,height[rk[i]]);

    cout << ans << endl;

}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建，使用 Stellar 作为主题。